package 中等.树;

import util.TreeNode;

/**
 * 有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，
 * 树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。
 * 最开始时：
 * 「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；
 * 「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。
 * 「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。
 * 之后两位玩家轮流进行操作，「一号」玩家先手。每一回合，玩家选择一个被他染过色的节点，
 * 将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色（「一号」玩家染红
 * 色，「二号」玩家染蓝色）。
 * 如果（且仅在此种情况下）当前玩家无法找到这样的节点来染色时，其回合就会被跳过。
 * 若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。
 * 现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这
 * 场游戏，则返回 true ；若无法获胜，就请返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/binary-tree-coloring-game
 */
public class 二叉树着色游戏_1145 {

    public static void main(String[] args) {

        //      3
        //         6
        //           7
        //          4
        //         1  2
        //            5
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        node5.right = node4;
        node4.left = node2;
        node2.left = node3;
        node2.right = node1;

        System.out.println(btreeGameWinningMove(node5, 5, 2));

    }

    /**
     * 贪心思想+深度搜索
     * 1，对于 x 节点可以选择它的父级节点，那么二号玩家的结节点数 = n - x及其子树所有节点
     * 2，或者选择 x 节点的左右子树中，节点数较多的子树，那么二号玩家的节点数为
     * Math.max(countNode(x.left),countNode(x.right))
     */
    public static boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        TreeNode xNode = findX(root, x);
        int xCnt = countNode(xNode);

        int lCnt = countNode(xNode.left);
        int rCnt = countNode(xNode.right);
        return (n - xCnt) > xCnt ? true : false || 2 * Math.max(lCnt, rCnt) - n > 0 ? true : false;
    }

    private static TreeNode findX(TreeNode node, int x) {
        if (node == null) {
            return null;
        }
        if (node.val == x) {
            return node;
        }

        TreeNode x1 = findX(node.left, x);
        TreeNode x2 = findX(node.right, x);
        if (x1 == null) {
            return x2;
        }
        return x1;
    }

    private static int countNode(TreeNode node) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null) {
            return 1;
        }
        return 1 + countNode(node.left) + countNode(node.right);
    }

}
